package algorithm.acwing.t851;

import java.io.*;
import java.util.Arrays;

public class Main {
    static class io {
        // 读
        static InputStreamReader ins = new InputStreamReader(System.in);
        static StreamTokenizer in = new StreamTokenizer(ins);
        static BufferedReader br = new BufferedReader(ins);

        // 写
        public static PrintWriter out = new PrintWriter(System.out);


        public static int readInt() {
            try {
                in.nextToken();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }

        public static String readLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public static double readDouble() {
            try {
                in.nextToken();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return in.nval;
        }
    }

    static int N = 510;
    static int[] h = new int[N], e = new int[N*N], ne = new int[N*N], edge = new int[N*N];
    static int idx = 0;
    static int[] dist = new int[N], st = new int[N];
    static void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = h[a];
        edge[idx] = c;
        h[a] = idx ++;
    }
    static int n = io.readInt(), m = io.readInt();
    public static void main(String[] args) {
        Arrays.fill(dist, Integer.MAX_VALUE/2);
        Arrays.fill(h, -1);
        for(int i = 1; i <= m; i ++) {
            int a = io.readInt(), b = io.readInt(), c = io.readInt();
            add(a, b, c);
        }
        dijkstra();

    }

    private static void dijkstra() {
        dist[1] = 0;
        for(int i = 1; i <= n; i ++) {
            int t = -1;
            for(int j = 1; j <= n; j++) {
                if(st[j] == 0 && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            if(t == -1) {
                break;
            }
            st[t] = 1;
            for(int j = h[t]; j != -1; j=ne[j]) {
                int point = e[j];
                dist[point] = Math.min(dist[point], dist[t] + edge[j]);
            }
        }
        if(dist[n] == Integer.MAX_VALUE/2) {
            io.out.println(-1);
        } else {
            io.out.println(dist[n]);
        }
        io.out.flush();
    }
}
